package 二叉树;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class NC15求二叉树的层序遍历 {

    /**
     * 如题,注意是每层一个集合
     * [
     * [1],
     * [2],
     * [3]
     * ]
     */

    //推崇比较传统的队列非递归解法  下面有递归解法

    private ArrayList<ArrayList<Integer>> levelOrderQueue(TreeNode root) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();

        if(root==null){
            return result;
        }

        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()){

            //当前队列的数量就是一层的数量 提起记录好当前一层的数量
            int count=queue.size();

            result.add(new ArrayList<>());
            while (count>0){
                TreeNode node = queue.removeFirst();
                count--;
                result.get(result.size()-1).add(node.val);
                if(node.left!=null) {
                    queue.addLast(node.left);
                }
                if(node.right!=null){
                    queue.addLast(node.right);
                }
            }

        }

        return result;
    }

    private ArrayList<ArrayList<Integer>> result;

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        result=new ArrayList<>();
        dfs(0,root);
        return result;
    }

    private void dfs(int deep,TreeNode node){
        if(node==null){
            return;
        }
        if(deep+1>result.size()){
            result.add(new ArrayList<>());
        }
        result.get(deep).add(node.val);
        dfs(deep+1,node.left);
        dfs(deep+1,node.right);
    }

    public static void main(String[] args) {

    }

}
